package array;
import java.util.*;
public class Ex128III {
    static class Solution {
        //暴力法：O(nlogn)
        public int longestConsecutive1(int[] nums) {
            int len;
            if (nums == null || (len = nums.length) == 0) return 0;
            Arrays.sort(nums);
            int lastStart = 1, maxLen = 1;
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < len; i++) {
                if (list.size() == 0 || nums[i] > list.peekLast()) list.offerLast(nums[i]);
            }

            System.out.println(list);
            for (int i = 1; i < list.size(); i++) {
                // System.out.println(list.peekLast() + " " + list.get(list.size() - 2));
                if (list.get(i) == list.get(i - 1) + 1) lastStart++;
                else lastStart = 1;
                maxLen = Math.max(maxLen, lastStart);
            }
            return maxLen;
        }

        //哈希表法
        //containsKey()、get()、put()、remove()都需要遍历一遍map，因此时间复杂度都是O(N),且加上一层外层循环，因此时间复杂度o(n^2)
        public int longestConsecutive2(int[] nums) {
            int len;
            if (nums == null || (len = nums.length) == 0) return 0;
            // Arrays.sort(nums);
            Map<Integer, Integer> map = new TreeMap<>();

            for (int i = 0; i < len; i++) {
                if (map.containsKey(nums[i])) map.put(nums[i], map.get(nums[i]) + 1);
                else map.put(nums[i], 1);
            }
            int lastKey = Integer.MAX_VALUE, max = 0, con = 0;
            for (Integer key: map.keySet()) {
                if (key == lastKey + 1) con++;
                else con = 1;
                lastKey = key;
                max = Math.max(max, con);
            }
            return max;
        }


        //哈希表法，优化
        // 错误。因为乱序不可能达到效果
        public int longestConsecutive3(int[] nums) {
            int max = 0, len;
            if (nums == null || (len = nums.length) == 0) return 0;
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < len; i++) {
                if (map.containsKey(nums[i] - 1)) map.put(nums[i], map.get(nums[i - 1]) + 1);
                else map.put(nums[i], 1);
            }

            for (Integer k: map.keySet()) {
                max = Math.max(max, map.get(k));
            }
            return max;
        }

        //并查集法，需要首先定义并查集类
        public int longestConsecutive(int[] nums) {
            int max = 0, len;
            if (nums == null || (len = nums.length) == 0) return 0;
            UnionFindSet ufs = new UnionFindSet(nums);

            for (int num : nums) {
                max = Math.max(ufs.union(num, num + 1), max);
            }
            return max;
        }

        class UnionFindSet {

            //使用Map存储，防止数组长度不确定造成的越界
            Map<Integer, Integer> parent;

            //当前某集合的元素数量
            //key:当前集合的根节点；
            //val:以这个根节点作为父节点的元素个数；
            Map<Integer, Integer> weight;

            int[] nums;
            //初始化并查集
            public UnionFindSet(int[] nums) {
                int len = nums.length;
                this.nums = nums;
                parent = new HashMap<>();
                weight = new HashMap<>();
                for (int i = 0; i < len; i++) {
                    parent.put(nums[i], nums[i]);
                    weight.put(nums[i], 1);
                }
            }

            //返回根节点
            public int find(int num) {
                while (num != parent.get(num)) 
                num = parent.get(num);
                return num;
            } 

            //接收：当前元素num以及num + 1
            //返回：以num所在集合的根节点为根的集合元素个数
            //只有***tar包含在nums中，才会进行合并***
            public int union(int num, int tar) {
                if (!parent.containsKey(tar)) {
                    //因为在初始化时，所有的元素都会变成一个key，而tar不是key，说明tar不是nums元素
                    //不是nums元素，不进行合并，直接返回当前元素所在集合个数
                    return weight.get(find(num));
                }

                int r = find(num);
                int t = find(tar);

                //本来就是同一个集合，不合并
                if (r == t) return weight.get(num);
                parent.put(tar, r);
                int sum = weight.get(r) + weight.get(t);

                //将主分支元素作为“根节点”的元素个数
                weight.put(r, sum);
                return sum;
            }
            
            //只需要 构造、并、查 三个方法即可
        }
    }

    

    public static void main(String[] args) {
        Solution s = new Solution();
        // int nums[] = new int[]{1,2,0,1};
        // int nums2[] = new int[] {100,4,200,1,3,2};
        int nums2[] = new int[] {0,3,7,2,5,8,4,6,0,1};
        int res = s.longestConsecutive(nums2);
        System.out.println(Math.pow(10, 9) > Integer.MAX_VALUE);
        System.out.println(res);
    }

}
